package 二分查找;

import javax.sound.midi.MidiChannel;
import java.util.HashMap;
import java.util.Map;
import java.util.NavigableMap;

public class LCR173点名7 {
    //https://leetcode.cn/problems/que-shi-de-shu-zi-lcof/description/
    public int takeAttendance1(int[] records) {
        int[] hash = new int[records.length + 1];
        for (int record : records) {
            hash[record]++;
        }
        for (int i = 0; i < records.length; i++) {
            if (hash[i] == 0) return i;
        }
        return records.length;
    }
    public int takeAttendance2(int[] records) {
        for (int i = 0; i < records.length; i++) {
            if ((i ^ records[i]) != 0) return i; // != 也一样
        }
        return records.length;
    }
    public static int takeAttendance3(int[] records) {
        double sum1 = records.length *((double)(records.length + 1) / 2);
        int sum2 = 0;
        for (int x : records) {
            sum2 += x;
        }
        return (int) sum1 - sum2;
    }

    public static void main(String[] args) {
        int[] array = new int[] {0,1,2,3,4,5,6,8};
        takeAttendance3(array);
    }


    public int takeAttendance(int[] records) {
        int left = 0, right = records.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if(records[mid] == mid) left = mid + 1;
            else right = mid;
        }
//        if(records[left] == left) return records.length;
//        return left;
        return records[left] == left ? left + 1 : left;
    }

}
